#include <iostream>
#include <random>
#include <cmath>
#include <ctime>
#include <vector>
#include <algorithm>

using namespace std;

class mergeSort
{
	friend class comparator;
public:
	mergeSort();
	~mergeSort();
	static void merge(std::vector<int> &v,size_t left,size_t mid,size_t right);
	static void sort(std::vector<int> &v,size_t low,size_t high);
};
void mergeSort::sort(std::vector<int> &array,size_t low,size_t high){
	if (low<high)
	{
		size_t mid = low + ((high-low)>>1);		//更加安全，可以防止数组过大发生溢出
		sort(array,low,mid);
		sort(array,mid+1,high);
		merge(array,low,mid,high);
	}
}
void mergeSort::merge(std::vector<int> &array,size_t low,size_t mid,size_t high){
	std::vector<int> help;
	size_t p1=low;
	size_t p2=mid+1;
	while(p1<=mid&&p2<=high){
		int value = array[p1]<=array[p2]?array[p1++]:array[p2++];	//为保证算法的稳定性，此处需要使用<=,此处假设升序排列
		help.push_back(value);
	}
	while(p1<=mid){
		help.push_back(array[p1++]);
	}
	while(p2<=high){
		help.push_back(array[p2++]);
	}
	auto ivec=array.begin()+low;
	for(auto value:help){
		*ivec = value;		//可合并为*ivec++=value;
		ivec++;
	}
}

class Comparator{
public:
	std::vector<int> geneArr();
	void printVector(const std::vector<int>& v){
		for(auto value:v){
			cout<<value<<" ";
		}
		cout<<endl;
	}
	void operator()(){
		cout<<"排序前："<<endl;
		std::vector<int> array1 = geneArr();
		printVector(array1);
		cout<<"-------------------------------------------------------------"<<endl;
		std::vector<int> array2(array1);
		printVector(array2);
		cout<<"排序后："<<endl;
		sort(array1.begin(),array1.end());
		printVector(array1);
		cout<<"-------------------------------------------------------------"<<endl;
		mergeSort::sort(array2,0,array2.size()-1);
		printVector(array2);
		if (array1==array2)
		{
			/* code */
			cout<<"success"<<endl;
		}
	}
};
std::vector<int> Comparator::geneArr(){
	static default_random_engine e(time(0));
	static uniform_int_distribution<int> u(-1000,10000);
	std::vector<int> v;
	for(size_t i=0;i<abs(u(e)%100);i++){
		v.push_back(u(e));
	}
	return v;
}
int main(){
	Comparator comparator;
	comparator();
	return 0;
}
